//给定一个无序的整数数组，找到其中最长上升子序列的长度。 
//
// 示例: 
//
// 输入: [10,9,2,5,3,7,101,18]
//输出: 4 
//解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 
//
// 说明: 
//
// 
// 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 
// 你算法的时间复杂度应该为 O(n2) 。 
// 
//
// 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗? 
// Related Topics 二分查找 动态规划
package leetcode.editor.cn;

import java.util.Objects;

//Java：Longest Increasing Subsequence
public class P300LongestIncreasingSubsequence{
    public static void main(String[] args) {
        Solution solution = new P300LongestIncreasingSubsequence().new Solution();
        // TO TEST
        int[] test = {10,9,2,5,3,7,101,18};
        int result = solution.lengthOfLIS(test);
        System.out.println(result);
    }
    

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(Objects.isNull(nums) || nums.length == 0){
            return 0;
        }
        int defaultValue = 1;
        int length = nums.length;
        int[] dp = new int[length ];
        for(int i=0;i<length;i++){
            dp[i] = 1;
        }
        for(int i=0;i<length;i++){
            for(int j=0;j<i;j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            defaultValue = Math.max(defaultValue, dp[i]);
        }
        return defaultValue;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
